# Square of the sum of the first n natural number
# f(n) = (1 + 2 + 3 + 4 + ... + n)^2
# f(n) = [n * (1 + n) / 2]^2
#
# Sum of the square of the first n natural number
# g(n) = 1^2 + 2^2 + 3^2 + ... + n^2
#
# n    : 0,  1,  2,  3,  4,  5,  6, ...
# n^2  : 0,  1,  4,  9, 16, 25, 36, ...
# g(n) : 0,  1,  5, 14, 30, 55, 91, ...
# diff1:     1,  4,  9, 16, 25, 36, ...
# diff2:         3,  5,  7,  9, 11, ...
# diff2:             2,  2,  2,  2, ...
#
# The third derivation look constant so maybe we can say
# g(n) = a*n^3 + b*n^2 + c*n + d
#
# With g(0), g(1), g(2), g(3), we will find a, b, c, d
# V = [ 0,  0,  0,  1] * [a] = [ 0] : g0
#     [ 1,  1,  1,  1] * [b] = [ 1] : g1
#     [ 8,  4,  2,  1] * [c] = [ 5] : g2
#     [27,  9,  3,  1] * [d] = [14] : g3
# So d = 0
# ---
# V = [ 1,  1,  1] * [a] = [ 1] : g1
#     [ 8,  4,  2] * [b] = [ 5] : g2
#     [27,  9,  3] * [c] = [14] : g3
# ---
# V = [ 1,  1,  1] * [a] = [ 1] : g1
#     [ 6,  2,  0] * [b] = [ 3] : g2 - 2*g1 = v1
#     [24,  6,  0] * [c] = [11] : g3 - 3*g1 = v2
# ---
# V = [ 1,  1,  1] * [a] = [ 1] : g1
#     [ 6,  2,  0] * [b] = [ 3] : v1
#     [ 6,  0,  0] * [c] = [ 2] : v2 - 3*v1 = v3
# ---
# V = [ 1,  1,  1] * [a] = [ 1] : g1
#     [ 0,  2,  0] * [b] = [ 1] : v1 - v3
#     [ 3,  0,  0] * [c] = [ 1] : v3/2
# So a, b, c, d = 1/3, 1/2, 1/6, 0
# g(n) = n^3/3 + n^2/2 + n/6
# g(n) = 1/6 * (2*n^3 + 3*n^2 + n)
# g(n) = 1/6 * n * (2*n^2 + 3*n + 1)
# g(n) = 1/6 * n * (2*n + 1) * (n + 1)
#
# This function is true for n = 0, 1, 2, 3
# Verify this property is true for all other n
# (n + 1)^2 = n^2 + 2*n + 1
# (n + 1)^3 = n^3 + 3*n^2 + 3*n + 1
# g(n+1) = g(n) + (n+1)^2
# g(n+1) = 1/6 * (2*n^3 + 3*n^2 + n) + n^2 + 2*n + 1
# g(n+1) = 1/6 * (2*n^3 + 3*n^2 + n + 6*n^2 + 12*n + 6)
# g(n+1) = 1/6 * (2*n^3 + 9*n^2 + 13*n + 6)
# g(n+1) = 1/6 * (2*(n + 1)^3 + 3*n^2 + 7*n + 4)
# g(n+1) = 1/6 * (2*(n + 1)^3 + 3*(n+1)^2 + (n + 1))
# if g(n) formula is true then g(n+1) formula is true

def Solve():
    n = 100
    fn = (n*(1 + n)/2)**2
    gn = n * (2*n + 1) * (n + 1) / 6
    return fn - gn

